//给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 
//
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 
//
// 示例: 
//
// 给定的有序链表： [-10, -3, 0, 5, 9],
//
//一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
//
//      0
//     / \
//   -3   9
//   /   /
// -10  5
// 
// Related Topics 树 二叉搜索树 链表 分治 二叉树 
// 👍 612 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class ConvertSortedListToBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new ConvertSortedListToBinarySearchTree().new Solution();
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 根据提供的有序链表来创建平衡二叉搜索树
     * 要是把链表转换成数组就没意思了(题解真有这么做的，但是这题与前一题的目的就是要使用链表来实现)
     * 主流的实现方式：使用快慢双指针进行递归，将链表分割成前后两部分，然后分别构建左右平衡二叉搜索树
     * 快慢指针就是：慢指针每次前进一，快指针每次前进二，当快指针到链表尾时，慢指针正好到达中间位置
     * 需要另一个指针来储存慢指针的前一个节点，这样便于将前后链表断开
     * 下边这个方法就是快慢指针的方法
     */
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;//如果当前链表为空的话直接返回null

        ListNode slow = head;//慢指针
        ListNode fast = head;//快指针
        ListNode preSlow = null;//慢指针的前驱节点

         //TODO 这里遍历结束之后慢指针指向的节点就可以作为当前树的根节点了
        while (fast!=null&&fast.next!=null){//根据快指针进行判断
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);//创建根节点

        if (preSlow!=null){//前驱节点不为null说明左子树还需要继续创建
            preSlow.next = null;//这里一定要将前部分链表与后边断开才行
            root.left = sortedListToBST(head); //将当前根节点的左子节点设置为新的树
        }
        root.right = sortedListToBST(slow.next);
        return root;//返回建立完成的根节点
    }



    public Integer[] getNums(ListNode head){
        List<Integer> list = new LinkedList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        Integer[] nums = list.toArray(new Integer[list.size()]);
        return nums;
    }
    public TreeNode arrayToTree(Integer[] nums, int low, int high){//这里传入的是右闭区间
        if (low>high) return null;
        int mid = (low + high)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = arrayToTree(nums, low, mid-1);
        root.right = arrayToTree(nums, mid+1, high);
        return root;
    }

    /**
     * 二刷，既然是给的链表，那么直接根据链表转换数组去的中间值去切片构建，而且是平衡的
     * 此次区间是左闭右开的
     */
    public TreeNode sortedListToBST2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head!=null) {
            list.add(head.val);
            head = head.next;
        }
        int[] nums = list.stream().mapToInt(Integer::intValue).toArray();
        //所有区间左闭右开
        return slicing(nums, 0, nums.length);
    }

    public TreeNode slicing(int[] nums, int start, int end){
        if (start == end) return null;
        int index = start + (end - start) /2;
        TreeNode root = new TreeNode(nums[index]);
        if (end - start == 1) return root;
        root.left = slicing(nums, start, index);
        root.right = slicing(nums, index+1, end);
        return root;
    }










}
//leetcode submit region end(Prohibit modification and deletion)

}















































